import java.util.HashMap;

class Solution {
    public int strStr(String haystack, String needle) {
        int nLength = needle.length();
        if (nLength == 0) {
            return 0;
        }

        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i <= haystack.length() - nLength; i++) {
            String str = haystack.substring(i, i + nLength);
            if (!map.containsKey(str)) {
                map.put(str, i);
            }
        }
        Integer index = map.get(needle);
        return index == null ? -1 : index;
    }
}